"""
    这是快速排序算法，使用快慢交换指针实现
"""
import random


class QuickSort:
    def __init__(self, arr):
        self.arr = arr
        self.length = len(arr)
        self.i = 0

    def quicksort(self, pleft, pright):
        """
        分治递归的进行快速排序
        :param pleft: 左指针（慢）
        :param pright: 右指针（快）
        :return: None
        """
        if(pleft < pright):         # 递归条件
            begin = pleft           # 要记录本次递归起始点，作为下一次递归的输入
            end = pright
            tag = 1     # 1:right指针移动；0：left指针移动
            base_index = random.randint(pleft, pright)      # 随机选取基准元素
            base_value = self.arr[base_index]
            while pleft != pright:              # 快速排序结束条件
                if tag == 1:
                    if self.arr[pright] > self.arr[base_index]:     # 注意：因为是随机确定基准元素，所以不能让右指针越过基准
                        pright -= 1
                    else:
                        tag = 0

                else:
                    # 左指针只有在右指针满足条件的时候才会移动，所以这时左指针完全可以越过基准，就好像将基准设定为首元素一样
                    if self.arr[pleft] <= self.arr[base_index]:
                        pleft += 1
                    else:
                        if pright == base_index:        # 右指针停在基准位置重合是特殊情况，要记住基准元素的移动
                            base_index = pleft
                            temp = self.arr[pright]
                            self.arr[pright] = self.arr[pleft]
                            self.arr[pleft] = temp
                            tag = 1
                        else:
                            temp = self.arr[pright]
                            self.arr[pright] = self.arr[pleft]
                            self.arr[pleft] = temp
                            tag = 1
            temp = self.arr[pleft]                  # 最后，当左右指针重合时，交换重合元素与基准元素完成快速排序
            self.arr[pleft] = self.arr[base_index]
            self.arr[base_index] = temp
            self.i += 1
            print(f"选取{base_value}作为基准元素：第{self.i}趟排序结果：{self.arr}")
            self.quicksort(begin, pleft-1)
            self.quicksort(pleft+1, end)
        else:
            return


s1 = [5, 1, 0, 2, 6, 3, 4, 7, 9, 8]
s2 = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
c = QuickSort(s1)
c.quicksort(0, 9)
print(f"共经历{c.i}次排序，最终输出结果为：{c.arr}")







